README.md

572. Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example 1:

Given tree s:

 3 / \ 4 5 / \ 1 2 

Given tree t:

 4 / \ 1 2 

Return true, because t has the same structure and node values with a subtree of s.

Example 2:

Given tree s:

 3 / \ 4 5 / \ 1 2 / 0 

Given tree t:

 4 / \ 1 2 

Return false.

Solutions (Python)

1. Compare Nodes

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution: defisSubtree(self, s: TreeNode, t: TreeNode) ->bool: defisEqual(s: TreeNode, t: TreeNode) ->bool: ifsandtands.val==t.val: returnisEqual(s.left, t.left) andisEqual(s.right, t.right) elifnotsandnott: returnTrueelse: returnFalsereturnsand (isEqual(s, t) orself.isSubtree(s.left, t) orself.isSubtree(s.right, t))

2. Convert to String

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution: defisSubtree(self, s: TreeNode, t: TreeNode) ->bool: deftoString(root: TreeNode) ->str: ifnotroot: return'N'return"~%d%s%s"% (root.val, toString(root.left), toString(root.right)) returntoString(t) intoString(s)